package com.zdp.algorithm.stackandqueue;

import lombok.extern.slf4j.Slf4j;

import java.util.Stack;

/**
 * 用一个栈 对 另一个栈 进行排序
 * 从顶到底，按从大到小排序
 * @author Zhengdp
 * @date 2023年01月08日 11:09
 */
@Slf4j
public class SortStackByStack {

    private static final int[] elements = new int[]{
            6,3,4,5,7,8
    };

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        for(int element : elements) {
            stack.push(element);
        }
        sortStackByStack(stack);
        log.info("从大到小排序");
        while(!stack.isEmpty()) {
            log.info("{}",stack.pop());
        }
    }

    /**
     * 辅助栈的数据是 stack 中压入的
     * 辅助栈的数据从顶到底 应该是 从小到大排序的
     * 问题的关键就是如何保证 辅助栈的数据顺序
     * 1. stack弹出数据cur,若cur的值小于等于 辅助栈栈顶元素，将cur压入辅助栈
     * 2. 如果cur值大于辅助栈栈顶元素，将辅助栈栈顶元素压入stack，重复该过程，
     * 直到cur值小于等于辅助栈栈顶元素
     * @param stack
     */
    private static void sortStackByStack(Stack<Integer> stack) {
        Stack<Integer> help = new Stack<>();
        while(!stack.isEmpty()) {
            int cur =  stack.pop();
            while(!help.isEmpty() && cur > help.peek()) {
                stack.push(help.pop());
            }
            help.push(cur);
        }
        while (!help.isEmpty()) {
            stack.push(help.pop());
        }
    }
}


